#include <stdio.h>
#include <stdlib.h>
#include "wlist.h"

int list_create(List_st **ptr,INSERT insert)
{
	List_st *newnode = NULL;
	List_st *last = NULL;
	while(1)
	{
		int num;
		scanf("%d",&num);
		if(num == -1)
		{
			break;	
		}
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return -1;
		newnode->data = num;
		newnode->next = NULL;

		switch(insert)
		{
			case head:
				{
					list_insert_head(ptr,newnode);
					break;
				}
			case end:
				{
					list_insert_end(ptr,&last,newnode);
					break;
				}
			case order:	
				{	
					list_insert_order(ptr,newnode);
					break;
				}
		}
	}
}

/*头插法
 *
 */

void list_insert_head(List_st **Head,List_st *newnode)
{
	if(*Head == NULL)
	{
		*Head = newnode;
	}
	else
	{
		newnode->next = *Head;
		*Head = newnode;
	}
}

/*尾插法
 *
 *
 */

void list_insert_end(List_st **Head,List_st **last,List_st *newnode)
{
	if(*Head == NULL)
	{
		*Head = newnode;
		*last = newnode;
	}
	else
	{
		(*last)->next = newnode;
		*last = newnode;
	}
}
/*顺序插入
 *@prev:待插入点的前驱
 *@cur:插入点的位置
 */

void list_insert_order(List_st **Head,List_st *newnode)
{
	List_st *prev = NULL;
	List_st *cur = *Head;
	//如果为第一个结点，头结点就是新结点
	if(*Head == NULL)
	{
		*Head = newnode;
	}
	else
	{
		//找合适插入位置
		while(cur)
		{
			if(cur->data > newnode->data)
			{
				break;
			}
			else
			{
				prev = cur;
				cur = cur->next;
			}
		}
		//没找到就插到尾部	
		if(cur == NULL)
		{
			prev->next = newnode;
		}
		else
		{
			//位置是头结点		
			if(cur == *Head)
			{
				newnode->next = *Head;
				*Head = newnode;
			}
			//位置为中间任意结点		
			else
			{
				newnode->next = prev->next;
				prev->next = newnode;
			}
		}


	}


}



List_st * list_delete(List_st *ptr,Datatype *data)
{
	if(NULL == ptr)
		return NULL;
	List_st *cur = ptr;
	List_st *prev = NULL;

	while(cur)
	{
		if(cur->data == *data)
		{
			break;
		}
		prev = cur;
		cur = cur->next;
	}

	if(cur == NULL)
	{
		return ptr;
	}
	else
	{
		if(cur == ptr)
		{
			ptr = cur->next;
			cur->next = NULL;
		}
		else if(cur->next == NULL)
		{
			prev->next = NULL;
		}
		else
		{
			prev->next = cur->next;
			cur->next = NULL;
		}
		free(cur);
	}
}

List_st * list_delete_all(List_st *ptr,Datatype *data)
{
	if(NULL == ptr)
		return NULL;
	List_st *cur = ptr;
	List_st *prev = NULL;
	while(1)
	{
		while(cur)
		{
			if(cur->data == *data)
			{
				break;
			}
			prev = cur;
			cur = cur->next;
		}

		if(cur == NULL)
		{
			return ptr;
		}
		else
		{
			if(cur == ptr)
			{
				ptr = cur->next;
				cur->next = NULL;
			}
			else if(cur->next == NULL)
			{
				prev->next = NULL;
			}
			else
			{
				prev->next = cur->next;
				cur->next = NULL;
			}
			free(cur);
		}
		cur = prev->next;
	}
}

	int list_nodenumber(List_st *ptr)
	{
		int sum = 0;
		for(;ptr;ptr = ptr->next)
			sum++;
		return sum;	
	}

	List_st *list_lastnode(List_st *ptr)
	{
		for(;ptr->next;ptr = ptr->next);
		return ptr;
	}

	void list_display(List_st *p)
	{
		List_st *ptr;
		for(ptr = p;ptr;ptr = ptr->next)
		{
			printf("%d ",ptr->data);
		}
		printf("\n");

	}
